FreeCore Function #15:
Linear Feedback Shift Register (LFSR)
Module name: lfsr
Current release: version 1.0, November 5, 1997
Contributed by: Woody Johnson woodyj@dacmail.net

Introduction

Shown below is the schematic representation of the module:

This is a design that can be used to implement a linear feedback shift register (LFSR) of various lengths.  Such registers are useful for replacing counters when the count sequence is unimportant (such as in implementing fifo head and tail pointers) or were only the terminal count value is used.

Theory of Operation

The design starts out with an output value of 0 upon assertion of reset and counts through a pseudo-random sequence of 2^(n-1) states were n is the number of taps, or bits, in the LFSR.  The LFSR state with all bits equal to 1's is an illegal state which is never entered upon normal operation.  This implementation uses XNOR feedback so that the state of all 0's is legal (as opposed to XOR feedback were the all 0's state is illegal).  The illegal state of an LFSR is one such that the value of the LFSR would never change due to the fact that the feedback term causes the current state to be self propagating.  Shown below is a simulation of the above implementaion of a 3-bit LFSR.

The Prev[] outputs are optional.  One possible use for the Prev[] is when using LFSR's as head and tail pointers for implementing fifos.  The empty state is entered upon a pop when tail pointer is equal to the previous head pointer, and similarily, the full state is entered upon a push when head pointer is equal to previous tail pointer.  Note that the reset state of Prev[] is correctly set to the value previous to the all zero's reset state of the LFSR Q[] outputs.

The Next[] outputs are also optional.  One possible use for the Next[] pointer is shown in the schematic above.  When Next[] == 0, then the counter is at its terminal count.  Note that the lsb of Next[] is a combinatorial output.

Module Parameters

Enjoy!

Last updated 08 Feb 2001 11:53